package com.leecode.base;

/**
 * @ClassName Index_15_希尔排序
 * @Author bsy
 * @Description  插入类排序- 希尔排序
 * 设计思想：
 * 把整体元素以gap为间距进行分组，每组之间进行直接插入排序，排序完之后再以gap/2继续排序，直至gap为1为止。
 * 本质是插入排序，只不过这个插入排序和gap有关系 ，尽量把小的数据快速往前移，把大的数据快速往后移（相对于相邻分组的好处）
 *
 * 稳定性：
 * 稳定性：不稳定
 * 时间复杂度：O(n的1.3平方)【估计】，与gap增量有关
 * 空间复杂度：O(1)
 * 元素越有序，直接插入排序速度越快（理解成插入排序的优化）【对数据敏感】
 *
 *
 * @Date 2023/2/19 15:42
 * @Version 1.0
 */
public class Index_15_希尔排序 {

    public static void main(String[] args) {
        int[] nums = {1, 5, 8, 3, 2, 5, 6};
        int[] ints = sellSort(nums);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(i);
        }

    }

    public static int[] sellSort(int[] nums) {

        int d = nums.length / 2;
        while (d > 1) {
            for (int i = 0; i < d; i++) {
                if (nums[i] > nums[i + d]) {
                    int temp = nums[i];
                    nums[i] = nums[i + d];
                    nums[i + d] = temp;
                } else {
                    break;
                }
            }
            d = d / 2;  //每次将步长折半
        }

        return nums;
    }
}
